#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数 */

#define STACK_MAX_SIZE 100 // 栈最多支持存放100个数据元素

#define bool int

/*算符间的优先关系表(+,-,*,/,(,),#)*/
char cpri[7][7]={
     {'>','>','<','<','<','>','>' },
     {'>','>','<','<','<','>','>' },
     {'>','>','>','>','<','>','>' },
     {'>','>','>','>','<','>','>' },
     {'<','<','<','<','<','=',' '},
     {'>','>','>','>',' ','>','>'},
     {'<','<','<','<','<',' ','='}
    };

/*定义栈的函数*/
typedef struct stack {
  int * base;
  int * top;
  int number_of_elements; // 栈内实际数据元素个数
} * Stack;

// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack * s){
	(*s) = (Stack )malloc(sizeof(Stack));
	(*s)->base = (int *)malloc(STACK_MAX_SIZE * sizeof(int));
	if(!(*s)->base)
		return 1;  //存储分配失败，返回error
	(*s)->top = (*s)->base;  //分配成功则让栈顶指针指向栈底指针
	(*s)->number_of_elements = STACK_MAX_SIZE;
	return 0;
}

// 只返回栈顶元素，通过result变量返回栈顶元素的值。函数返回值用于表示执行状态：0，成功；1，不成功。
int get_top(Stack s, char * symbol){
	//int result; 
	if(s->top == s->base){
		return 1;
	}
	(*symbol) = *(s->top);
	return 0;
}

// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand){
	if(s->top - s->base >= s->number_of_elements){
		return 1;
	}
	*(++s->top) = operator_or_operand;
	//(s->top)++;
	return 0;
}

int pop(Stack s, char * p_operator_or_operand){
	if(s->top == s->base) {//判断是否栈空
		return 0;
	}
	*p_operator_or_operand = *(s->top);
	s->top--;
	return 1;
}

// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
int is_optr(char symbol){
	switch(symbol){
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
	case '#':
			return 1;
	default: return 0;
	}
}

/*返回运算符在数组中的索引*/
int demo(char c){
	int in;
	switch(c){
	case '+': in = 0;break;
	case '-': in = 1;break;
	case '*': in = 2;break;
	case '/': in = 3;break;
	case '(': in = 4;break;
	case ')': in = 5;break;
	case '#': in = 6;break;
	default: return -1;
	}
	return in;
}

/*运算符优先级的判定*/
char precede(char top,char c)
{
 int i,j;
 i=demo(top);
 j=demo(c);
 return cpri[i][j];
}

//运算函数
char operate(char a,char theta,char b)
{
	int a1,b1;
	char result=0;
	a1 = a - '0';
	b1 = b - '0';
 
 switch(theta)
 {
  case '+':
   result = (char)((a1+b1)+'0');
   break;
  case '-':
   result = (char)((a1-b1)+'0');
   break;
  case '*':
   result = (char)((a1*b1)+'0');
   break;
  case '/':
   result = (char)((a1/b1)+'0');
   break;
 }
 return result;
}


// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
bool is_operator(char symbol){
	if(symbol == '+' || symbol == '-' ||symbol == '*' ||symbol == '/' ||
		symbol == '(' ||symbol == ')' ||symbol == '#'){
		return 1;
	}
	return 0;
}

// 判断刚扫描到的symbol是否操作数。如果symbol是操作数，返回1，否则返回0。
bool is_operand(char symbol){
	if(symbol >= '1'&& symbol <= '9' ){
	return 1;
	}
	return 0;
}

// 用于计算表达式的值，比如#3*(2+6)/4#。
// 返回值表示求值状态：0，合法表达式，成功求值；1，表达式不合法。
// result变量用于返回计算结果。
int evaluate(char * expression, int * result)
{
 int k = 1;
 char c=0,theta=0;
 char e=1;
 char a=0,b=0;
 Stack OPND;
 Stack OPTR;
 init_stack(&OPTR);
 init_stack(&OPND);
 c = expression[k];
 k++;
 push(OPTR,expression[0]);
 while( expression[k]!= '#' ||e!='#'){
	 if(is_operand(c)){
		push(OPND,c);
		c = expression[k]; //读取下一字符c = '#'
		if(c != '#'){
			k++;
		}
	 }
	 if(is_operator(c)){
		 get_top(OPTR,&e);
		 switch(precede(e,c))
			 {
				case '<':
				 push(OPTR,c);
				 c = expression[k];//栈顶元素的优先权低//c = '2'
				 if(c != '#'){
					k++;//expression[k]=='#'
				get_top(OPTR,&e);
				}
				 break;
				case '=': //脱括号并接受下一字符
				 pop(OPTR,&c);
				 c = expression[k];//c = *
				 k++;//expression[k]=='2'
				 break;
				case '>': //退栈并将运算结果入
				 pop(OPTR,(char*)&theta); 
				 pop(OPND,(char*)&b);
				 pop(OPND,(char*)&a);
				 push(OPND,operate(a,theta,b));
				 get_top(OPTR,&e);
				 break;  
		   }
	 } else{
		return 1;
	 }
 }
 get_top(OPND,&e);
 *result =  e - '0';
 return *result;
}

int main(){
	char *symbol = "#3*(2+6)/4#";
	int result=0;
	evaluate(symbol,&result);
	printf("%d",result);
	system("pause");
	
}
